class UnionFind:
    def __init__(self, grid):
        row = len(grid)
        col = len(grid[0])
        self.count = row * col
        self.root = [i for i in range(row * col)]

    def find(self, x):
        if x != self.root[x]:
            # 将该节点的根节点递归改为鼻祖根节点
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.root[rootx] = rooty
            self.count -= 1

    def get_count(self):
        return self.count


def numIslands(grid):
    if not grid:
        return 0
    row = len(grid)
    col = len(grid[0])
    waters = 0
    uf = UnionFind(grid)
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '0':
                waters += 1
            else:
                directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
                for d in directions:
                    x = i + d[0]
                    y = j + d[1]
                    if x >= 0 and x < row and y >= 0 and y < col and grid[x][y] == '1':
                        uf.union(x * col + y, i * col + j)
    return uf.get_count() - waters


grid = [["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]]
print(numIslands(grid))
